package Z.dailyExercise.March;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Map;

public class _169多数元素 {
    /**
     * 直接方法：借助hash表
     * @param nums
     * @return
     */
    public int majorityElement(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int num:nums){
            map.put(num,map.getOrDefault(num,0)+1);
        }

        int res =0;
        for (int count:map.keySet()){
            if (map.get(count) > nums.length/2){
                res = count;
                break;
            }
        }
        return res;

    }

    /**
     * 空间复杂度降到1
     * 题解：摩尔投票法
     */
    public int majorityElement1(int[] nums) {
        int candidate = nums[0];
        int vote = 1;

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] ==candidate){
                vote++;
            }else {
                vote--;
            }

            if (vote ==0){
                candidate = nums[i+1];
                vote=0;

            }


        }

        return candidate;
    }

}
